package cn.initcap.algorithm.graph.util;

import cn.initcap.algorithm.graph.Graph;
import cn.initcap.algorithm.graph.SparseGraph;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 哈密尔顿路径
 *
 * @author initcap
 * @date Created in 7/31/19 9:54 AM.
 */
public class HamiltonPath {

    private Graph<Integer, Double> graph;
    private int[] pre;
    private int end;
    private int s;

    /**
     * 用户需要传入一个起始点，因为在图中有的起点会有路径，有的没有
     *
     * @param graph
     * @param s
     */
    public HamiltonPath(Graph graph, int s) {
        this.graph = graph;
        end = -1;
        this.s = s;
        pre = new int[graph.nodeSize()];
        int visited = 0;
        // 从任意一个定点开始都可以
        dfs(s, s, graph.nodeSize(), visited);
    }

    public static void main(String[] args) {
        Graph graph = new SparseGraph("algorithm/testG12.txt", false);
        HamiltonPath dfs = new HamiltonPath(graph, 1);
        System.out.println(dfs.result());
    }

    private boolean dfs(int v, int parent, int count, int visited) {
        visited += (1 << v);
        pre[v] = parent;
        count--;
        if (count == 0) {
            end = v;
            return true;
        }

        for (int w : graph.adj(v)) {
            if ((visited & (1 << w)) == 0) {
                if (dfs(w, v, count, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    public List<Integer> result() {
        List<Integer> res = new ArrayList<>();
        if (end == -1) {
            return res;
        }

        int cur = end;
        while (cur != s) {
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

}
